package com.mlh.binarytree.search;

import com.mlh.binarytree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author 缪林辉
 * @date 2024/3/25 11:48
 * @DESCRIPTION
 */

//二叉树的先序遍历
public class PreorderTraversal {
    //方法一：递归
    public List<Integer> method1(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        recursion(root,res);
        return res;
    }

    public void recursion(TreeNode node,List<Integer>list){
        if(node==null){
            return;
        }
        list.add(node.val);
        recursion(node.left,list);
        recursion(node.right,list);

    }

    //方法二：栈
    //根节点先入栈
    //然后弹出栈，输出节点值
    //最后先右后左将子节点入栈
    public List<Integer> method2(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }
        List<Integer> res=new ArrayList<>();
        Stack<TreeNode>stack=new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            res.add(pop.val);
            if(pop.right!=null){
                stack.push(pop.right);
            }
            if (pop.left!=null){
                stack.push(pop.left);
            }
        }
        return res;
    }

    public List<Integer> practice(TreeNode root){
        if(root==null){
            return new ArrayList<>();
        }
        List<Integer>res=new ArrayList<>();
        LinkedList<TreeNode>stack=new LinkedList<>();
        stack.addLast(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pollLast();
            res.add(node.val);
            if(node.right!=null){
                stack.addLast(node.right);
            }
            if(node.left!=null){
                stack.addLast(node.left);
            }
        }
        return res;
    }
}
